Context-Free Grammars (CFGs) and Parsing Expression Grammars (PEGs) haveseveral similarities and a few differences in both their syntax and semantics,but they are usually presented through formalisms that hinder a propercomparison. In this paper we present a new formalism for CFGs that highlightsthe similarities and differences between them. The new formalism borrows fromPEGs the use of parsing expressions and the recognition-based semantics. Weshow how one way of removing non-determinism from this formalism yields aformalism with the semantics of PEGs. We also prove, based on these newformalisms, how LL(1) grammars define the same language whether interpreted asCFGs or as PEGs, and also show how strong-LL(k), right-linear, and LL-regulargrammars have simple language-preserving translations from CFGs to PEGs.
展开▼
